package cn.edu.cdu.group4nb.utils;

public class SortUtils {
    /**
     *冒泡排序
     * @param attr 用于排序的数
     * @return 排好的数
     * 过程：每次从最后一个数开始和相邻的数进行比较，小于就向上，每一趟把最小的放到参加本次冒泡的数的最前面，注意二层循环的j>i
     */
    public static int[]  bubbleSort(int[] attr){
        int temp;//交换时临时存储变量
        boolean flag;//用于减少外层循环次数
        for (int i=0;i<attr.length-1;i++){//有多少个数就循环多少次
            flag=false;//如果冒完一趟都还是false，说明已经排好序，不用再循环外层
            for (int j=attr.length-1;j>i;j--) {//把最下面的数和临近的数相比较，交换。并且不和排好队的比较交换（j>i）
                if (attr[j] < attr[j -1]) {//满足条件就交换
                    temp = attr[j];
                    attr[j] = attr[j -1];
                    attr[j - 1] = temp;
                    flag=true;
                }
            }
            if (!flag) break;//如果冒完一趟都还是false，说明已经排好序，不用再循环外层
        }
        return attr;
    }

    /**
     *  选择排序
     *   过程:每次在为排序的数字中取出最小值和第一个数字交换
     *   1.找到最小值
     *    2.交换
     * @param arr
     * @return
     */
    public static int[] selectionSort(int[] arr) {
        for (int i =0;i<arr.length;i++){//有多少数就循环多少次,用于交换的索引i，每次用于交换都不一样
            int minIndex=i;//真实最小值的索引，首先最小值的索引为0
            for (int j=i;j<arr.length;j++){ //此循环的目的是找出最小值，第一次是从所有数中找到最小的数和第一个数交换（j=i）
                if (arr[j]<arr[minIndex]){//如果最小值
                    minIndex=j;
                }
            }//循环完之后找到最小值minIndex
            //交换
            if (minIndex!=i){//如果最小值就是第一个，就不交换了
                int temp=arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
        }
        return arr;
    }

    /**
     * 插入排序
     * @param arr
     * @return
     */
    public static int[]  insertSort(int arr[]){
        int temp;//存储当前指针指向的值
        int leftindex;//排好的索引
        for (int i=1;i<arr.length;i++){//刚开始指针指向第二个数字
//            将此指针指向的数和前面的进行比较，直到找到比他更小的数字
            temp=arr[i];
            leftindex=i-1;
            while(leftindex>=0 && arr[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
                arr[leftindex+1] = arr[leftindex];
                leftindex--;
            }
            arr[leftindex+1] = temp;//把temp放到空位上
            }

        return arr;
    }
}

